On the impact of initialisation strategies on Maximum Flow algorithm performance

Abstract

Due to its theoretical and practical importance in network theory, designing effective algorithms for the Maximum Flow Problem (MFP) remains a focus of research efforts. Although worst-case performance analysis is the main tool for examining performance, empirical analysis across a wide variety of benchmark cases can identify scenarios where practical performance may contradict theoretical worse-case. In our previous work, we used Instance Space Analysis (ISA) to identify the practical strengths and weaknesses of four state-of-the-art MFP algorithms, and identified that the arc/path finding strategies employed by the algorithms explain critical differences in the algorithms’ behaviours. In t..